package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-11 13:28
 **/
public class LeetCode1036 {

    //被围住
    static final int BLOCKED = 0;

    //到达target
    static final int FOUND = 1;

    //不在圈内
    static final int OVER = 2;

    //上下左右
    static final int[][] DIRS = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        int n = blocked.length;
        //如果n <= 1则围不住任何一个点
        if (n <= 1) {
            return true;
        }

        //障碍能够围住的最大范围
        int max = n * (n - 1) / 2;

        //使用集合存储阻塞点映射的一维值
        Set<Integer> blocks = new HashSet<>();
        for (int[] ints : blocked) {
            blocks.add(convert(ints[0], ints[1]));
        }


        //广度遍历所有节点
        int result = bfs(source, target, blocks, max);

        //如果被围住,返回false,如果找到target,返回true
        if (result == BLOCKED) {
            return false;
        } else if (result == FOUND) {
            return true;
        }

        //如果是source没有被包围,就需要判断target没有被包围
        return bfs(target, source, blocks, max) != BLOCKED;
    }

    /**
     *
     * @param source
     * @param target
     * @param blocks
     * @return
     */
    int bfs(int[] source, int[] target, Set<Integer> blocks, int max) {
        //存储需要遍历的节点
        Queue<int[]>  queue = new LinkedList<>();
        queue.add(source);
        //记录访问过的点
        Set<Integer> visited = new HashSet<>();
        visited.add(convert(source[0], source[1]));

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();

            for (int[] dir : DIRS) {
                int x = poll[0] + dir[0];
                int y = poll[1] + dir[1];

                //如果当前的(x,y)坐标是合法的,不是障碍也没有被访问过
                int num = convert(x, y);
                if (x >= 0 && x < 1000000 && y >= 0 && y < 1000000 && !visited.contains(num) && !blocks.contains(num)) {
                    //找到target,直接返回FOUND
                    if (x == target[0] && y == target[1]) {
                        return FOUND;
                    }

                    //标记当前点已访问
                    visited.add(convert(x, y));

                    //如果访问集合大小 > max,说明source没有被障碍包围, 返回Over
                    if (visited.size() > max) {
                        return OVER;
                    }
                    //添加到队列中
                    queue.add(new int[]{x, y});
                }

            }
        }

        //被包围
        return BLOCKED;
    }

    /**
     * 将二维坐标转为一维的值,如果出现冲突,就换一个系数,或者双hash
     * @param x
     * @param y
     * @return
     */
    int convert(int x, int y) {
        return 100 * x + y;
    }
}
